【题解】 Tyvj1730二逼平衡树 树套树 luogu3380/bzoj3196

树套树，直接线段树套 $Splay$ .

因为有区间的$k$大，不能直接用$Splay$(大佬忽视这句话)，显然可以用树套树(废话)。对于每一个线段树的节点都建一棵 $Splay$ ，需要查询这个节点所代表的区间第 $k$ 大等操作时直接用 $Splay$ 来完成即可……

但是，如果不是正好的区间呢？假如询问区间横跨了两个子树区间怎么办呢？

这就需要技巧了.

下面，对于第一个操作，先贴出代码:

inline void Seg_rank(int x,int l,int r,int L,int R,int Kth){
    if(l==L&&r==R){ans+=Splay_rank(x,Kth);return;}//必须判断啊，一定要相等
    if(R<=mid)Seg_rank(lc,l,mid,L,R,Kth);//完全属于左子树
    else if(L>mid)Seg_rank(rc,mid+1,r,L,R,Kth);//完全属于左子树
    else Seg_rank(lc,l,mid,L,mid,Kth),Seg_rank(rc,mid+1,r,mid+1,R,Kth);
    //因为 ans 是 += ，所以直接拆开即可，因为有些抽象，可以画图模拟
};

case 1:{IN(v);ans=0;Seg_rank(1,1,n,x,y,v);printf("%d\n",ans+1);}break;

基本上，所有有关的操作都可以参考上面的代码段……

多说无益，直接看代码吧.

哦，对了，其实理解只需纸笔和一份正确的代码，并不要太多的讲解(感觉网上没找到很优秀的文章……)

Code:

#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#define ll long long
#define RI register int 
#define A printf("A")
#define C printf(" ")
#define inf 2147483647
#define PI 3.1415926535898
using namespace std;
const int N=4e6+2;
//template <typename _Tp> inline _Tp max(const _Tp&x,const _Tp&y){return x>y?x:y;} 
//template <typename _Tp> inline _Tp min(const _Tp&x,const _Tp&y){return x<y?x:y;}
template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	if(flag)x=-x;
}
int n,m,a[N],ans,MX;
/*----------------------------------Splay-------------------------------------*/
int f[N],c[N],s[N],v[N],ch[N][2],rt[N],tot;
// rt[i] 表示线段树编号为i的节点的Splay的根节点
inline int chk(int x){return ch[f[x]][1]==x;};
inline void Splay_del_node(int x){f[x]=s[x]=c[x]=v[x]=ch[x][0]=ch[x][1]=0;};
inline void Splay_pushup(int x){s[x]=(ch[x][0]?s[ch[x][0]]:0)+(ch[x][1]?s[ch[x][1]]:0)+c[x];};
inline void Splay_rotate(int x){
	int y=f[x],z=f[y],k=chk(x),v=ch[x][k^1];
	ch[y][k]=v;if(v)f[v]=y;f[x]=z;if(z)ch[z][chk(y)]=x;
	f[y]=x,ch[x][k^1]=y;Splay_pushup(y),Splay_pushup(x);
};
inline void Splay(int i,int x,int top=0){
	 while(f[x]!=top){
        int y=f[x],z=f[y];
        if(z!=top)Splay_rotate((ch[z][0]==y)==(ch[y][0]==x)?y:x);
        Splay_rotate(x);
    }if(!top)rt[i]=x;
};
inline void Splay_Insert(int i,int x){
	int pos=rt[i];
	if(!rt[i]){
	    rt[i]=pos=++tot;v[pos]=x;s[pos]=c[pos]=1;
        f[pos]=ch[pos][0]=ch[pos][1]=0;return;
	}int last=0;
	while(1){
	    if(v[pos]==x){++c[pos];Splay_pushup(last);break;}
        last=pos;pos=ch[pos][x>v[pos]];
        if(!pos){
            pos=++tot;v[pos]=x;s[pos]=c[pos]=1;
            ch[last][x>v[last]]=pos;
            f[pos]=last;ch[pos][0]=ch[pos][1]=0;
            Splay_pushup(last);break;
        }
	}Splay(i,pos);return;
};
inline int Splay_rank(int i,int k){
	int x=rt[i],cal=0;
	while(x){
	    if(v[x]==k)return cal+((ch[x][0])?s[ch[x][0]]:0);
	    else if(v[x]<k){
	        cal+=((ch[x][0])?s[ch[x][0]]:0)+c[x];x=ch[x][1];
	    }else x=ch[x][0];
	}return cal;
};
inline int Splay_find(int i,int x){
 	int pos=rt[i];while(x){
	    if(v[pos]==x){Splay(i,pos);return pos;};
		pos=ch[pos][x>v[pos]];
	}return 0;
};
inline int Splay_pre(int i){int x=ch[rt[i]][0];while(ch[x][1])x=ch[x][1];return x;}
inline int Splay_suc(int i){int x=ch[rt[i]][1];while(ch[x][0])x=ch[x][0];return x;}
inline int Splay_Get_pre(int i,int x){
    int pos=rt[i];while(pos){
        if(v[pos]<x){if(ans<v[pos])ans=v[pos];pos=ch[pos][1];}
        else pos=ch[pos][0];
    }return ans;
};
inline int Splay_Get_suc(int i,int x){
    int pos=rt[i];while(pos){
        if(v[pos]>x){if(ans>v[pos])ans=v[pos];pos=ch[pos][0];}
        else pos=ch[pos][1];
    }return ans;
};
inline void Splay_Delete(int i,int key){
    int x=Splay_find(i,key);
    if(c[x]>1){--c[x];Splay_pushup(x);return;}
    if(!ch[x][0]&&!ch[x][1]){Splay_del_node(rt[i]);rt[i]=0;return;}
    if(!ch[x][0]){int y=ch[x][1];rt[i]=y;f[y]=0;return;}
	if(!ch[x][1]){int y=ch[x][0];rt[i]=y;f[y]=0;return;}
	int p=Splay_pre(i);int lastrt=rt[i];
	Splay(i,p,0);ch[rt[i]][1]=ch[lastrt][1];f[ch[lastrt][1]]=rt[i];
	Splay_del_node(lastrt);Splay_pushup(rt[i]);
};
/*------------------------------Seg_Tree--------------------------------------*/ 
#define lc ((x)<<1)
#define rc ((x)<<1|1)
#define mid ((l+r)>>1)
inline void Seg_Insert(int x,int l,int r,int pos,int val){
    Splay_Insert(x,val);if(l==r)return;
    if(pos<=mid)Seg_Insert(lc,l,mid,pos,val);
	else Seg_Insert(rc,mid+1,r,pos,val);
};
inline void Seg_rank(int x,int l,int r,int L,int R,int Kth){
    if(l==L&&r==R){ans+=Splay_rank(x,Kth);return;}
    if(R<=mid)Seg_rank(lc,l,mid,L,R,Kth);
    else if(L>mid)Seg_rank(rc,mid+1,r,L,R,Kth);
    else Seg_rank(lc,l,mid,L,mid,Kth),Seg_rank(rc,mid+1,r,mid+1,R,Kth);
};
inline void Seg_change(int x,int l,int r,int pos,int val){
//    printf("QvQ:: %d %d %d %d %d\n",x,l,r,pos,val);
	Splay_Delete(x,a[pos]);Splay_Insert(x,val);
    if(l==r){a[pos]=val;return;};
    if(pos<=mid)Seg_change(lc,l,mid,pos,val);
    else Seg_change(rc,mid+1,r,pos,val);
};
inline void Seg_pre(int x,int l,int r,int L,int R,int val){
    if(l==L&&r==R){ans=max(ans,Splay_Get_pre(x,val));return;}
    if(R<=mid)Seg_pre(lc,l,mid,L,R,val);
    else if(L>mid)Seg_pre(rc,mid+1,r,L,R,val);
    else Seg_pre(lc,l,mid,L,mid,val),Seg_pre(rc,mid+1,r,mid+1,R,val);
};
inline void Seg_suc(int x,int l,int r,int L,int R,int val){
    if(l==L&&r==R){ans=min(ans,Splay_Get_suc(x,val));return;}
    if(R<=mid)Seg_suc(lc,l,mid,L,R,val);
    else if(L>mid)Seg_suc(rc,mid+1,r,L,R,val);
    else Seg_suc(lc,l,mid,L,mid,val),Seg_suc(rc,mid+1,r,mid+1,R,val);
};
/*---------------------------------ask----------------------------------------*/
inline int Get_Kth(int x,int y,int k){
    int L=0,R=MX+1,M;
    while(L<R){
        M=(L+R)>>1;
        ans=0;Seg_rank(1,1,n,x,y,M);
        if(ans<k)L=M+1;else R=M;
    }return L-1;
};
/*-------------------------------main-------------------------------------*/
int main(int argc,char const* argv[]){
    IN(n),IN(m);
    for(RI i=1;i<=n;++i){IN(a[i]);Seg_Insert(1,1,n,i,a[i]);MX=max(MX,a[i]);}
    while(m--){
        int op,x,y,v;IN(op),IN(x),IN(y);
        switch(op){
            case 1:{IN(v);ans=0;Seg_rank(1,1,n,x,y,v);printf("%d\n",ans+1);}break;
            case 2:{IN(v);printf("%d\n",Get_Kth(x,y,v));}break;
            case 3:{Seg_change(1,1,n,x,y);}break;
            case 4:{IN(v);ans=-inf;Seg_pre(1,1,n,x,y,v);printf("%d\n",ans);}break;
            case 5:{IN(v);ans=inf;Seg_suc(1,1,n,x,y,v);printf("%d\n",ans);}break;
        }
    }return 0;
}

本文标题:【题解】 Tyvj1730二逼平衡树 树套树 luogu3380/bzoj3196

文章作者:Qiuly

发布时间:2019年02月13日 - 00:00

最后更新:2019年03月29日 - 13:52

原始链接:http://qiulyblog.github.io/2019/02/13/[题解]luoguP1730/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

题解 树套树

【题解】 楼房重建 线段树 bzoj2957

【题解】 [NOI2014]魔法森林 动态加边Spfa bzoj3669/luogu2387